package com.hdu.point_offer;

public class lcr132 {
    class Solution {
        public int cuttingBamboo(int n) {
            if (n == 2) return 1;
            if (n == 3) return 2;
            int mod = 1000000007;
            int tail = (n % 3 == 0 ? 1 : (n % 3 == 1 ? 4 : 2));
            int pow = (tail == 1 ? n : (n - tail)) / 3;
            return (int) (pow(3, pow, mod) * tail % mod);
        }

        long pow(long x, int n, int mod)
        {
            long ans = 1;
            while (n != 0)
            {
                if ((n & 1) != 0)
                {
                    ans = ans * x % mod;
                }
                x = x * x % mod;
                n /= 2;
            }
            return ans;
        }
    }
}
